/* 
 * File:   FPTree.h
 * Author: wx
 *
 * Created on 2009年12月21日, 上午10:17
 */

#ifndef _FPTREE_H
#define	_FPTREE_H

#include <vector>
using namespace std;

#include "FPNode.h"
#include "HeadTable.h"
#include "Pattern.h"

class FPTree
{
private:
    HeadTable * ht;
    FPNode * root;
public:
    FPTree()
    {
        ht = NULL;
        root = NULL;
    }

    FPTree(vector<Transaction> & vt)
    {
        //need threshold
        ht = new HeadTable(vt);
        buildTree(vt);
    }

    FPTree(vector<Pattern> & pt,const HeadTable & ht)
    {
        //todo

        //create a new HeadTable with old one and the Pattern

        //buildTree with Pattern
    }

    

    //input;transaction db and threshold
    //output:FP-Tree,treeroot?
    void buildTree(vector<Transaction> & vt)
    {
        root = new FPNode(-1);
        for( int i = 0;i < vt.size();i++)
        {
            vector<int> tmp = vt[i].getFrequent(ht.getFreq());
            insert_tree(tmp,root);
        }
    }

    void void insert_tree(vector<int> freqitems,FPNode * curroot)
    {
        //empty
        if(freqitems.empty())return;

        //get the first item
        int firstitem = freqitems[0];
        FPNode * N;
        if( curroot->haschild(firstitem))
        {
            N = curroot->getChildNode(firstitem);
            N->increaseone();
        }
        else
        {
            //create,初始化数目是1，parent指针
            N = curroot->createChildNode(firstitem);
        }

        //the head table link
        ht.updateTable(N);
    }

    set<Pattern> getConditionalPattern(int i)
    {
        //从headtable的表开始查从下向上查
        set<Pattern> result;
        FPNode * head = ht->getHead(i);
        while( head != NULL)
        {
            result.insert(createConditonalPattern(head));
            head = head->getNext();
        }
        return result;
    }

private:
    //conditional pattern
    Pattern createConditionalPattern(FPNode * p)
    {
        Pattern p;
        p.setCount(p->getCount());
        FPNode * tmp = p;
        while(tmp != NULL)
        {
            p.addPattern(tmp->getItem());
            tmp = tmp->getParent();
        }
        
        return p;
    }
};

#endif	/* _FPTREE_H */

